merge2.c

   1 /*
   2  * wiggle - apply rejected patches
   3  *
   4  * Copyright (C) 2005 Neil Brown <neilb@cse.unsw.edu.au>
   5  * Copyright (C) 2010-2013 Neil Brown <neilb@suse.de>
   6  *
   7  *
   8  *    This program is free software; you can redistribute it and/or modify
   9  *    it under the terms of the GNU General Public License as published by
  10  *    the Free Software Foundation; either version 2 of the License, or
  11  *    (at your option) any later version.
  12  *
  13  *    This program is distributed in the hope that it will be useful,
  14  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *    GNU General Public License for more details.
  17  *
  18  *    You should have received a copy of the GNU General Public License
  19  *    along with this program.
  20  *
  21  *    Author: Neil Brown
  22  *    Email: <neilb@suse.de>
  23  */
  24
  25 #include "wiggle.h"
  26 #include <limits.h>
  27
  28 /*
  29  * Second attempt at merging....
  30  *
  31  * We want to create a mergelist which identifies 'orig' and 'after'
  32  * sections (from a and c) and conflicts (which are ranges of a,b,c which
  33  * all don't match).
  34  * It is also helpful to differentiate 'orig' sections that aren't
  35  * matched in 'b' with orig sections that are.
  36  * To help with highlighting, it will be useful to know where
  37  * the conflicts match the csl lists.
  38  *
  39  * This can all be achieved with a list of (a,b,c,c1,c1) 5-tuples.
  40  * If two consecutive differ in more than one of a,b,c, it is a
  41  * conflict.
  42  * If only 'a' differ, it is un-matched original.
  43  * If only 'b' differ, it is matched, unchanged original
  44  * If only 'c' differ, it is 1
  45  */
  46
  47 static inline int min(int a, int b)
  48 {
  49         return a < b ? a : b;
  50 }
  51
  52 static int check_alreadyapplied(struct file af, struct file cf,
  53                                 struct merge *m)
  54 {
  55         int i;
  56         if (m->al != m->cl)
  57                 return 0;
  58         for (i = 0; i < m->al; i++) {
  59                 if (af.list[m->a+i].len != cf.list[m->c+i].len)
  60                         return 0;
  61                 if (strncmp(af.list[m->a+i].start,
  62                             cf.list[m->c+i].start,
  63                             af.list[m->a+i].len) != 0)
  64                         return 0;
  65         }
  66         if (do_trace) {
  67                 printf("already applied %d,%d,%d - %d,%d,%d\n",
  68                        m->a, m->b, m->c, m->al, m->bl, m->cl);
  69                 printf(" %.10s - %.10s\n", af.list[m->a].start,
  70                        cf.list[m->c].start);
  71         }
  72         m->type = AlreadyApplied;
  73         return 1;
  74 }
  75
  76 /* A 'cut-point' is a location in the merger where it is reasonable
  77  * the change the mode of display - between displaying the merger
  78  * and displaying the separate streams.
  79  * A 'conflict' can only be displayed as separate stream so when
  80  * one is found, we need to find a preceding and trailing cut-point
  81  * and enlarge the conflict to that range.
  82  * A suitable location is one where all three streams are at a line-end.
  83  */
  84 static int is_cutpoint(struct merge m,
  85                        struct file af, struct file bf, struct file cf)
  86 {
  87         return ((m.a == 0 || ends_line(af.list[m.a-1])) &&
  88                 (m.b == 0 || ends_line(bf.list[m.b-1])) &&
  89                 (m.c == 0 || ends_line(cf.list[m.c-1])));
  90 }
  91
  92 int isolate_conflicts(struct file af, struct file bf, struct file cf,
  93                       struct csl *csl1, struct csl *csl2, int words,
  94                       struct merge *m, int show_wiggles,
  95                       int *wigglesp)
  96 {
  97         /* A Conflict indicates that something is definitely wrong
  98          * and so we need to be a bit suspicious of nearby apparent matches.
  99          * To display a conflict effectively we expands its effect to
 100          * include any Extraneous, Unmatched, Changed or AlreadyApplied text.
 101          * Also, unless 'words', we need to include any partial lines
 102          * in the Unchanged text that forms the border of a conflict.
 103          *
 104          * A Changed text may also border a conflict, but it can
 105          * only border one conflict (where as an Unchanged can border
 106          * a preceding and a following conflict).
 107          * The 'new' section of a Changed text appears in the
 108          * conflict as does any part of the original before
 109          * a newline.
 110          *
 111          * A hunk header (Extraneous) is never considered part of a
 112          * conflict.  It thereby can serve as a separator between
 113          * conflicts.
 114          *
 115          * Extended conflicts are marked by setting ->in_conflict in
 116          * the "struct merge".  This is '1' for an Unchanged, Changed,
 117          * or (Extraneous) hunk header which borders the conflict,
 118          * '2' for a merger which is truly in conflict, and '3' for
 119          * a merger which is causing a 'wiggle'.
 120          * When in_conflict == 1, the 'lo' and 'hi' fields indicate
 121          * how much of the 'a' file is included in the conflict, the rest
 122          * being part of the clean result.
 123          * Elements in af from m->a to m->a+m->lo are in the preceding
 124          * conflict, from m->a+m->lo to m->a+m->hi are clean, and
 125          * m->a+m->hi to m->a+m->al are in the following conflict.
 126          *
 127          * We need to ensure there is adequate context for the conflict.
 128          * So ensure there are at least 3 newlines in Extraneous or
 129          * Unchanged on both sides of a Conflict - but don't go so far
 130          * as including a hunk header.
 131          * If there are 3, and they are all in 'Unchanged' sections, then
 132          * that much context is not really needed - reduce it a bit.
 133          *
 134          * If a wiggle is adjacent to a conflict then:
 135          * - if show_wiggles is set, we just merge them
 136          * - if it is not set, we still want to count the wiggle.
 137          */
 138         int i, j, k;
 139         int cnt = 0, wiggles = 0;
 140         int in_wiggle = 0;
 141         int changed = 0;
 142         int unmatched = 0;
 143         int extraneous = 0;
 144
 145         for (i = 0; m[i].type != End; i++)
 146                 m[i].in_conflict = 0;
 147
 148         for (i = 0; m[i].type != End; i++) {
 149                 /* The '3' here is a count of newlines.  Once we find
 150                  * that many newlines of the particular type, we have escaped.
 151                  */
 152                 if (m[i].type == Changed)
 153                         changed = 3;
 154                 if (m[i].type == Unmatched)
 155                         unmatched = 3;
 156                 if (m[i].type == Extraneous && bf.list[m[i].b].start[0])
 157                         /* hunk headers don't imply wiggles, other
 158                          * extraneous text does.
 159                          */
 160                         extraneous = 3;
 161
 162                 if (m[i].type != Unchanged && changed && (unmatched || extraneous)) {
 163                         if (!in_wiggle)
 164                                 wiggles++;
 165                         in_wiggle = 1;
 166                 } else
 167                         in_wiggle = 0;
 168
 169                 if ((m[i].type == Conflict) ||
 170                     (show_wiggles && in_wiggle)) {
 171                         /* We have a conflict or wiggle here.
 172                          * First search backwards for an Unchanged marking
 173                          * things as in_conflict.  Then find the
 174                          * cut-point in the Unchanged.  If there isn't one,
 175                          * keep looking.
 176                          *
 177                          * Then search forward doing the same thing.
 178                          */
 179                         int newlines = 0;
 180                         m[i].in_conflict = m[i].type == Conflict ? 2 : 3;
 181                         j = i;
 182                         while (--j >= 0) {
 183                                 int firstk;
 184
 185                                 if (m[j].type == Extraneous &&
 186                                     bf.list[m[j].b].start[0] == '\0')
 187                                         /* hunk header - not conflict any more */
 188                                         break;
 189                                 if (m[j].in_conflict > 1)
 190                                         /* Merge the conflicts */
 191                                         break;
 192                                 if (!m[j].in_conflict) {
 193                                         m[j].in_conflict = 1;
 194                                         m[j].lo = 0;
 195                                 }
 196                                 /* Following must set m[j].hi, or set
 197                                  * in_conflict > 1
 198                                  */
 199                                 if (m[j].type == Extraneous) {
 200                                         for (k = m[j].bl; k > 0; k--)
 201                                                 if (ends_line(bf.list[m[j].b+k-1]))
 202                                                         newlines++;
 203                                 }
 204
 205                                 if (m[j].type != Unchanged &&
 206                                     m[j].type != Changed) {
 207                                         if (m[j].type == Conflict)
 208                                                 m[j].in_conflict = 2;
 209                                         else
 210                                                 m[j].in_conflict = m[i].in_conflict;
 211                                         continue;
 212                                 }
 213                                 /* If we find enough newlines in this section,
 214                                  * then we only really need 1, but would rather
 215                                  * it wasn't the first one.  'firstk' allows us
 216                                  * to track which newline we actually use
 217                                  */
 218                                 firstk = m[j].al+1;
 219                                 if (words) {
 220                                         m[j].hi = m[j].al;
 221                                         break;
 222                                 }
 223                                 /* need to find the last line-break, which
 224                                  * might be after the last newline, if there
 225                                  * is one, or might be at the start
 226                                  */
 227                                 for (k = m[j].al; k > 0; k--) {
 228                                         if (m[j].a + k >= af.elcnt)
 229                                                 /* FIXME impossible!*/
 230                                                 break;
 231                                         if (ends_line(af.list[m[j].a+k-1])) {
 232                                                 if (firstk > m[j].al)
 233                                                         firstk = k;
 234                                                 newlines++;
 235                                                 if (newlines >= 3) {
 236                                                         k = firstk;
 237                                                         break;
 238                                                 }
 239                                         }
 240                                 }
 241                                 if (k > 0)
 242                                         m[j].hi = k;
 243                                 else if (j == 0)
 244                                         m[j].hi = firstk;
 245                                 else if (is_cutpoint(m[j], af,bf,cf))
 246                                         m[j].hi = 0;
 247                                 else
 248                                         /* no start-of-line found... */
 249                                         m[j].hi = -1;
 250                                 if (m[j].hi > 0 &&
 251                                     (m[j].type == Changed)) {
 252                                         /* this can only work if start is
 253                                          * also a line break */
 254                                         if (is_cutpoint(m[j], af,bf,cf))
 255                                                 /* ok */;
 256                                         else
 257                                                 m[j].hi = -1;
 258                                 }
 259                                 if (m[j].hi >= 0)
 260                                         break;
 261                                 m[j].in_conflict = m[i].in_conflict;
 262                         }
 263
 264                         /* now the forward search */
 265                         newlines = 0;
 266                         for (j = i+1; m[j].type != End; j++) {
 267                                 if (m[j].type == Extraneous) {
 268                                         for (k = 0; k < m[j].bl; k++)
 269                                                 if (ends_line(bf.list[m[j].b+k]))
 270                                                         newlines++;
 271                                 }
 272                                 if (m[j].type != Unchanged &&
 273                                     m[j].type != Changed) {
 274                                         if (m[j].type == Conflict)
 275                                                 m[j].in_conflict = 2;
 276                                         else
 277                                                 m[j].in_conflict = m[i].in_conflict;
 278                                         continue;
 279                                 }
 280                                 m[j].in_conflict = 1;
 281                                 m[j].hi = m[j].al;
 282                                 if (words) {
 283                                         m[j].lo = 0;
 284                                         break;
 285                                 }
 286                                 /* need to find a line-break, which might be at
 287                                  * the very beginning, or might be after the
 288                                  * first newline - if there is one
 289                                  */
 290                                 if (is_cutpoint(m[j], af,bf,cf))
 291                                         m[j].lo = 0;
 292                                 else {
 293                                         /* If we find enough newlines in this section,
 294                                          * then we only really need 1, but would rather
 295                                          * it wasn't the first one.  'firstk' allows us
 296                                          * to track which newline we actually use
 297                                          */
 298                                         int firstk = -1;
 299                                         for (k = 0 ; k < m[j].al ; k++)
 300                                                 if (ends_line(af.list[m[j].a+k])) {
 301                                                         if (firstk < 0)
 302                                                                 firstk = k;
 303                                                         newlines++;
 304                                                         if (newlines >= 3) {
 305                                                                 k = firstk;
 306                                                                 break;
 307                                                         }
 308                                                 }
 309                                         if (newlines < 3 &&
 310                                             m[j+1].type  == End)
 311                                                 /* Hit end of file, pretend we found 3 newlines. */
 312                                                 k = firstk;
 313
 314                                         if (firstk >= 0 &&
 315                                             m[j+1].type == Unmatched) {
 316                                                 /* If this Unmatched exceeds 3 lines, just stop here */
 317                                                 int p;
 318                                                 int nl = 0;
 319                                                 for (p = 0; p < m[j+1].al ; p++)
 320                                                         if (ends_line(af.list[m[j+1].a+p])) {
 321                                                                 nl++;
 322                                                                 if (nl > 3)
 323                                                                         break;
 324                                                         }
 325                                                 if (nl > 3)
 326                                                         k = firstk;
 327                                         }
 328                                         if (k < m[j].al)
 329                                                 m[j].lo = k+1;
 330                                         else
 331                                                 /* no start-of-line found */
 332                                                 m[j].lo = m[j].al+1;
 333                                 }
 334                                 if (m[j].lo <= m[j].al+1 &&
 335                                     (m[j].type == Changed)) {
 336                                         /* this can only work if the end is a line break */
 337                                         if (is_cutpoint(m[j+1], af,bf,cf))
 338                                                 /* ok */;
 339                                         else
 340                                                 m[j].lo = m[j].al+1;
 341                                 }
 342                                 if (m[j].lo < m[j].al+1)
 343                                         break;
 344                                 m[j].in_conflict = m[i].in_conflict;
 345                         }
 346                         if (m[j-1].in_conflict == 1)
 347                                 i = j - 1;
 348                         else
 349                                 /* A hunk header bordered the conflict */
 350                                 i = j;
 351
 352                         /* If any of the merges are Changed or Conflict,
 353                          * then this really is a Conflict or Wiggle.
 354                          * If not they are just Unchanged, Unmatched,
 355                          * Extraneous or AlreadyApplied, and so don't
 356                          * really count.
 357                          * Note that the first/last merges (in_conflict==1)
 358                          * can be Changed and so much be check separately.
 359                          */
 360                         if (m[j].type == Changed)
 361                                 goto out;
 362                         for (j = i-1; j >= 0 && m[j].in_conflict > 1; j--)
 363                                 if (m[j].type == Changed || m[j].type == Conflict)
 364                                         goto out;
 365                         if (j >= 0 && m[j].type == Changed)
 366                                 goto out;
 367                         /* False alarm, no real conflict/wiggle here as
 368                          * nothing changed. */
 369                         if (j < 0)
 370                                 j = 0;
 371                         if (m[j].in_conflict == 1) {
 372                                 m[j].hi = m[j].al;
 373                                 if (m[j].lo == 0)
 374                                         m[j].in_conflict = 0;
 375                                 j++;
 376                         }
 377                         while (j <= i)
 378                                 m[j++].in_conflict = 0;
 379                 out:
 380                         if (m[i].type == End)
 381                                 break;
 382                 }
 383                 for (k = 1; k < m[i].al; k++) {
 384                         if (m[i].a + k >= af.elcnt)
 385                                 /* FIXME this should be impossible, but
 386                                  * it happened.
 387                                  */
 388                                 break;
 389                         if (words || ends_line(af.list[m[i].a+k])) {
 390                                 if (unmatched)
 391                                         unmatched--;
 392                                 if (changed)
 393                                         changed--;
 394                                 if (extraneous)
 395                                         extraneous--;
 396                         }
 397                 }
 398         }
 399         if (!show_wiggles)
 400                 *wigglesp = wiggles;
 401         /* Now count the conflicts and wiggles */
 402         for (i = 0; m[i].type != End; i++) {
 403                 int true_conflict = 0;
 404                 if (!m[i].in_conflict)
 405                         continue;
 406
 407                 for (j = i; m[j].type != End && m[j].in_conflict; j++) {
 408                         if (m[j].in_conflict == 2)
 409                                 true_conflict = 1;
 410                         if (j > i &&
 411                             m[j].in_conflict == 1) {
 412                                 /* end of region */
 413                                 if (!m[j+1].in_conflict)
 414                                         j++;
 415                                 break;
 416                         }
 417                 }
 418                 if (true_conflict)
 419                         cnt++;
 420                 else
 421                         wiggles++;
 422                 i = j-1;
 423         }
 424         if (show_wiggles)
 425                 *wigglesp = wiggles;
 426         return cnt;
 427 }
 428
 429 struct ci make_merger(struct file af, struct file bf, struct file cf,
 430                       struct csl *csl1, struct csl *csl2, int words,
 431                       int ignore_already, int show_wiggles)
 432 {
 433         /* find the wiggles and conflicts between csl1 and csl2
 434          */
 435         struct ci rv;
 436         int i, l;
 437         int a, b, c, c1, c2;
 438         int header_checked = -1;
 439         int header_found = 0;
 440
 441         rv.conflicts = rv.wiggles = rv.ignored = 0;
 442
 443         for (i = 0; csl1[i].len; i++)
 444                 ;
 445         l = i;
 446         for (i = 0; csl2[i].len; i++)
 447                 ;
 448         l += i;
 449         /* maybe a bit of slack at each end */
 450         l = l * 4 + 10;
 451
 452         rv.merger = xmalloc(sizeof(struct merge)*l);
 453
 454         a = b = c = c1 = c2 = 0;
 455         i = 0;
 456         while (1) {
 457                 int match1, match2;
 458                 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
 459                 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
 460
 461                 if (header_checked != c2) {
 462                         /* Check if there is a hunk header in this range */
 463                         int j;
 464                         header_found = -1;
 465                         for (j = b; j < csl2[c2].a + csl2[c2].len; j++)
 466                                 if (bf.list[j].start[0] == '\0') {
 467                                         header_found = j;
 468                                         break;
 469                                 }
 470                         header_checked = c2;
 471                 }
 472                 rv.merger[i].a = a;
 473                 rv.merger[i].b = b;
 474                 rv.merger[i].c = c;
 475                 rv.merger[i].c1 = c1;
 476                 rv.merger[i].c2 = c2;
 477                 rv.merger[i].in_conflict = 0;
 478
 479                 if (!match1 && match2) {
 480                         /* This is either Unmatched or Extraneous - probably both.
 481                          * If the match2 has a hunk-header Extraneous, it must
 482                          * align with an end-of-line in 'a', so adjust endpoint
 483                          */
 484                         int newa = csl1[c1].a;
 485                         if (header_found >= 0) {
 486                                 while (newa > a &&
 487                                        !ends_line(af.list[newa-1]))
 488                                         newa--;
 489                         }
 490                         if (a == newa && b == csl1[c1].b)
 491                                 newa = csl1[c1].a;
 492                         if (a < newa) {
 493                                 /* some unmatched text */
 494                                 rv.merger[i].type = Unmatched;
 495                                 rv.merger[i].al = newa - a;
 496                                 rv.merger[i].bl = 0;
 497                                 rv.merger[i].cl = 0;
 498                         } else {
 499                                 int newb;
 500                                 assert(b < csl1[c1].b);
 501                                 /* some Extraneous text */
 502                                 /* length is min of unmatched on left
 503                                  * and matched on right.
 504                                  * However a hunk-header must be an
 505                                  * Extraneous section by itself, so if this
 506                                  * start with one, the length is 1, and if
 507                                  * there is one in the middle, only take the
 508                                  * text up to there for now.
 509                                  */
 510                                 rv.merger[i].type = Extraneous;
 511                                 rv.merger[i].al = 0;
 512                                 newb = b +
 513                                         min(csl1[c1].b - b,
 514                                             csl2[c2].len - (b-csl2[c2].a));
 515                                 if (header_found == b) {
 516                                         newb = b + 1;
 517                                         header_checked = -1;
 518                                 } else if (header_found > b && header_found < newb) {
 519                                         newb = header_found;
 520                                         header_checked = -1;
 521                                 }
 522                                 assert(newb > b);
 523                                 rv.merger[i].cl =
 524                                         rv.merger[i].bl = newb - b;
 525                         }
 526                 } else if (match1 && !match2) {
 527                         /* some changed text
 528                          * if 'c' is currently at a suitable cut-point, then
 529                          * we can look for a triple-cut-point for start.
 530                          * Also, if csl2[c2].b isn't in a conflict, and is
 531                          * a suitable cut-point, then we could make a
 532                          * triple-cut-point for end of a conflict.
 533                          */
 534
 535                         rv.merger[i].type = Changed;
 536                         rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
 537                         rv.merger[i].al = rv.merger[i].bl;
 538                         rv.merger[i].cl = csl2[c2].b - c;
 539                 } else if (match1 && match2) {
 540                         /* Some unchanged text
 541                          */
 542                         rv.merger[i].type = Unchanged;
 543                         rv.merger[i].bl =
 544                                 min(csl1[c1].len - (b-csl1[c1].b),
 545                                     csl2[c2].len - (b-csl2[c2].a));
 546                         rv.merger[i].al = rv.merger[i].cl =
 547                                 rv.merger[i].bl;
 548                 } else {
 549                         /* must be a conflict.
 550                          * Move a and c to next match, and b to closest of the two
 551                          */
 552                         rv.merger[i].type = Conflict;
 553                         rv.merger[i].al = csl1[c1].a - a;
 554                         rv.merger[i].cl = csl2[c2].b - c;
 555                         rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
 556                         if (ignore_already &&
 557                             check_alreadyapplied(af, cf, &rv.merger[i]))
 558                                 rv.ignored++;
 559                         else if (rv.merger[i].bl == 0 &&
 560                                  rv.merger[i].cl > 0)
 561                                 /* As the 'before' stream is empty, this
 562                                  * could look like Unmatched in the
 563                                  * original, and an insertion in the
 564                                  * diff.  Reporting it like that is
 565                                  * probably more useful that as a full
 566                                  * conflict.
 567                                  * Leave the type for the insertion as
 568                                  * Conflict (not Changed) as there is some
 569                                  * real uncertainty here, but allow the
 570                                  * original to become Unmatched.
 571                                  */
 572                                 rv.merger[i].al = 0;
 573                 }
 574                 rv.merger[i].oldtype = rv.merger[i].type;
 575                 a += rv.merger[i].al;
 576                 b += rv.merger[i].bl;
 577                 c += rv.merger[i].cl;
 578                 i++;
 579
 580                 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
 581                         c1++;
 582                 assert(csl1[c1].b + csl1[c1].len >= b);
 583                 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
 584                         c2++;
 585                 assert(csl2[c2].a + csl2[c2].len >= b);
 586                 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
 587                     a == csl1[c1].a && b == csl1[c1].b &&
 588                     b == csl2[c2].a && c == csl2[c2].b)
 589                         break;
 590         }
 591         rv.merger[i].type = End;
 592         rv.merger[i].oldtype = End;
 593         rv.merger[i].a = a;
 594         rv.merger[i].b = b;
 595         rv.merger[i].c = c;
 596         rv.merger[i].c1 = c1;
 597         rv.merger[i].c2 = c2;
 598         rv.merger[i].in_conflict = 0;
 599         assert(i < l);
 600
 601         /* Now revert any AlreadyApplied that aren't bounded by
 602          * Unchanged or Changed.
 603          */
 604         for (i = 0; rv.merger[i].type != End; i++) {
 605                 if (rv.merger[i].type != AlreadyApplied)
 606                         continue;
 607                 if (i > 0 && rv.merger[i-1].type != Unchanged &&
 608                     rv.merger[i-1].type != Changed)
 609                         rv.merger[i].type = Conflict;
 610                 if (rv.merger[i+1].type != Unchanged &&
 611                     rv.merger[i+1].type != Changed &&
 612                     rv.merger[i+1].type != End)
 613                         rv.merger[i].type = Conflict;
 614         }
 615         rv.conflicts = isolate_conflicts(af, bf, cf, csl1, csl2, words,
 616                                          rv.merger, show_wiggles, &rv.wiggles);
 617         return rv;
 618 }
 619
 620 static int printrange(FILE *out, struct file *f, int start, int len,
 621                       int offset)
 622 {
 623         int lines = 0;
 624         while (len > 0 && start < f->elcnt) {
 625                 struct elmnt e = f->list[start];
 626                 printword(out, e);
 627                 if (e.start[e.plen-1] == '\n' &&
 628                     offset > 0)
 629                         lines++;
 630                 offset--;
 631                 start++;
 632                 len--;
 633         }
 634         return lines;
 635 }
 636
 637 static const char *conflict_types[] = {
 638         "", " border"," conflict"," wiggle" };
 639
 640 int print_merge(FILE *out, struct file *a, struct file *b, struct file *c,
 641                 int words, struct merge *merger,
 642                 struct merge *mpos, int streampos, int offsetpos)
 643 {
 644         struct merge *m;
 645         int lineno = 1;
 646         int rv = 0;
 647         int offset = INT_MAX;
 648         int first_matched;
 649
 650         for (m = merger; m->type != End ; m++) {
 651                 struct merge *cm;
 652                 if (do_trace)
 653                         printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
 654                                m->type==Unmatched ? "Unmatched" :
 655                                m->type==Unchanged ? "Unchanged" :
 656                                m->type==Extraneous ? "Extraneous" :
 657                                m->type==Changed ? "Changed" :
 658                                m->type==AlreadyApplied ? "AlreadyApplied" :
 659                                m->type==Conflict ? "Conflict":"unknown",
 660                                m->a, m->a+m->al-1,
 661                                m->b, m->b+m->bl-1,
 662                                m->c, m->c+m->cl-1,
 663                                conflict_types[m->in_conflict],
 664                                m->lo, m->hi);
 665
 666                 while (m->in_conflict) {
 667                         /* need to print from 'hi' to 'lo' of next
 668                          * Unchanged which is < it's hi
 669                          */
 670                         int found_conflict = 0;
 671                         int st = 0, st1;
 672                         if (m->in_conflict == 1)
 673                                 st = m->hi;
 674                         st1 = st;
 675
 676                         if (m == mpos)
 677                                 offset = offsetpos;
 678                         if (m->in_conflict == 1 && m->type == Unchanged)
 679                                 lineno += printrange(out, a, m->a+m->lo, m->hi - m->lo, offset - m->lo);
 680
 681                         if (m == mpos)
 682                                 rv = lineno;
 683                         if (do_trace)
 684                                 for (cm = m; cm->in_conflict; cm++) {
 685                                         printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}%s\n",
 686                                                cm->type==Unmatched?"Unmatched":
 687                                                cm->type==Unchanged?"Unchanged":
 688                                                cm->type==Extraneous?"Extraneous":
 689                                                cm->type==Changed?"Changed":
 690                                                cm->type==AlreadyApplied?"AlreadyApplied":
 691                                                cm->type==Conflict?"Conflict":"unknown",
 692                                                cm->a, cm->a+cm->al-1,
 693                                                cm->b, cm->b+cm->bl-1,
 694                                                cm->c, cm->c+cm->cl-1,
 695                                                conflict_types[m->in_conflict],
 696                                                cm->lo, cm->hi,
 697                                                (cm->type == Extraneous &&
 698                                                 b->list[cm->b].start[0] == '\0') ?
 699                                                b->list[cm->b].start+1: ""
 700                                         );
 701                                         if (cm->in_conflict == 1 && cm != m)
 702                                                 break;
 703                                 }
 704
 705                         if (m->in_conflict == 1 &&
 706                             m[1].in_conflict == 1) {
 707                                 /* Nothing between two conflicts */
 708                                 m++;
 709                                 continue;
 710                         }
 711
 712                         fputs(words ? "<<<---" : "<<<<<<< found\n", out);
 713                         if (!words)
 714                                 lineno++;
 715                         for (cm = m; cm->in_conflict; cm++) {
 716                                 if (cm == mpos && streampos == 0)
 717                                         offset = offsetpos;
 718                                 if (cm->type == Conflict)
 719                                         found_conflict = 1;
 720                                 if (cm->in_conflict == 1 && cm != m) {
 721                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 722                                         break;
 723                                 }
 724                                 lineno += printrange(out, a, cm->a+st1, cm->al-st1, offset-st1);
 725                                 st1 = 0;
 726                                 if (cm == mpos && streampos == 0)
 727                                         rv = lineno;
 728                         }
 729                         if (cm == mpos && streampos == 0)
 730                                 rv = lineno;
 731                 restart:
 732                         fputs(words ? "|||" : "||||||| expected\n", out);
 733                         if (!words)
 734                                 lineno++;
 735                         st1 = st;
 736                         first_matched = 1;
 737                         for (cm = m; cm->in_conflict; cm++) {
 738                                 if (cm->type == Extraneous &&
 739                                     b->list[cm->b].start[0] == '\0') {
 740                                         /* This is a hunk header, skip it and possibly
 741                                          * abort this section
 742                                          */
 743                                         if (first_matched)
 744                                                 continue;
 745                                         break;
 746                                 }
 747                                 if (cm->type != Unchanged && cm->type != Unmatched)
 748                                         first_matched = 0;
 749                                 if (cm == mpos && streampos == 1)
 750                                         offset = offsetpos;
 751                                 if (cm->in_conflict == 1 && cm != m) {
 752                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 753                                         break;
 754                                 }
 755                                 lineno += printrange(out, b, cm->b+st1, cm->bl-st1, offset-st1);
 756                                 st1 = 0;
 757                                 if (cm == mpos && streampos == 1)
 758                                         rv = lineno;
 759                         }
 760                         if (cm == mpos && streampos == 1)
 761                                 rv = lineno;
 762                         fputs(words ? "===" : "=======\n", out);
 763                         if (!words)
 764                                 lineno++;
 765                         st1 = st;
 766                         first_matched = 1;
 767                         for (cm = m; cm->in_conflict; cm++) {
 768                                 if (cm->type == Extraneous &&
 769                                     b->list[cm->b].start[0] == '\0') {
 770                                         /* This is a hunk header, skip it and possibly
 771                                          * abort this section and restart.
 772                                          */
 773                                         if (first_matched)
 774                                                 continue;
 775                                         m = cm;
 776                                         /* If remaining merges are all
 777                                          * Extraneous, Unchanged, or Unmatched,
 778                                          * we don't need them.
 779                                          */
 780                                         while (cm->in_conflict > 1 &&
 781                                                (cm->type == Extraneous ||
 782                                                 cm->type == Unmatched ||
 783                                                 cm->type == Unchanged))
 784                                                 cm ++;
 785                                         if (!cm->in_conflict)
 786                                                 /* Nothing more to report */
 787                                                 break;
 788                                         if (cm->in_conflict == 1 &&
 789                                                (cm->type == Extraneous ||
 790                                                 cm->type == Unmatched ||
 791                                                 cm->type == Unchanged))
 792                                                 /* border between conflicts, but
 793                                                  * still nothing to report.
 794                                                  */
 795                                                 break;
 796                                         fputs(words ? ">>>" : ">>>>>>> replacement\n", out);
 797                                         fputs(words ? "<<<" : "<<<<<<< found\n", out);
 798                                         st = 0;
 799                                         goto restart;
 800                                 }
 801                                 if (cm->type != Unchanged && cm->type != Unmatched)
 802                                         first_matched = 0;
 803                                 if (cm == mpos && streampos == 2)
 804                                         offset = offsetpos;
 805                                 if (cm->in_conflict == 1 && cm != m) {
 806                                         if (cm->type == Unchanged)
 807                                                 lineno += printrange(out, a, cm->a, cm->lo, offset);
 808                                         else
 809                                                 lineno += printrange(out, c, cm->c, cm->cl, offset);
 810                                         break;
 811                                 }
 812                                 if (cm->type == Changed)
 813                                         st1 = 0; /* All of result of change must be printed */
 814                                 lineno += printrange(out, c, cm->c+st1, cm->cl-st1, offset-st1);
 815                                 st1 = 0;
 816                                 if (cm == mpos && streampos == 2)
 817                                         rv = lineno;
 818                         }
 819                         if (cm == mpos && streampos == 2)
 820                                 rv = lineno;
 821                         if (!found_conflict) {
 822                                 /* This section was wiggled in successfully,
 823                                  * but full conflict display was requested.
 824                                  * So now print out the wiggled result as well.
 825                                  */
 826                                 fputs(words ? "&&&" : "&&&&&&& resolution\n", out);
 827                                 if (!words)
 828                                         lineno++;
 829                                 st1 = st;
 830                                 for (cm = m; cm->in_conflict; cm++) {
 831                                         int last = 0;
 832                                         if (cm->in_conflict == 1 && cm != m)
 833                                                 last = 1;
 834                                         switch (cm->type) {
 835                                         case Unchanged:
 836                                         case AlreadyApplied:
 837                                         case Unmatched:
 838                                                 lineno += printrange(out, a, cm->a+st1,
 839                                                                      last ? cm->lo : cm->al-st1, offset-st1);
 840                                                 break;
 841                                         case Extraneous:
 842                                                 break;
 843                                         case Changed:
 844                                                 lineno += printrange(out, c, cm->c,
 845                                                                      last ? cm->lo : cm->cl, offset);
 846                                                 break;
 847                                         case Conflict:
 848                                         case End:
 849                                                 assert(0);
 850                                         }
 851                                         if (last)
 852                                                 break;
 853                                         st1 = 0;
 854                                 }
 855                         }
 856                         fputs(words ? "--->>>" : ">>>>>>> replacement\n", out);
 857                         if (!words)
 858                                 lineno++;
 859                         m = cm;
 860                         if (m->in_conflict == 1 && m[1].in_conflict == 0) {
 861                                 /* End of a conflict, no conflict follows */
 862                                 if (m == mpos)
 863                                         offset = offsetpos;
 864                                 if (m->type == Unchanged)
 865                                         lineno += printrange(out, a, m->a+m->lo, m->hi-m->lo, offset-m->lo);
 866                                 if (m == mpos)
 867                                         rv = lineno;
 868                                 m++;
 869                         }
 870                 }
 871
 872                 /* there is always some non-conflict after a conflict,
 873                  * unless we hit the end
 874                  */
 875                 if (m->type == End)
 876                         break;
 877
 878                 if (do_trace) {
 879                         printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
 880                                m->type==Unmatched?"Unmatched":
 881                                m->type==Unchanged?"Unchanged":
 882                                m->type==Extraneous?"Extraneous":
 883                                m->type==Changed?"Changed":
 884                                m->type==AlreadyApplied?"AlreadyApplied":
 885                                m->type==Conflict?"Conflict":"unknown",
 886                                m->a, m->a+m->al-1,
 887                                m->b, m->b+m->bl-1,
 888                                m->c, m->c+m->cl-1,
 889                                conflict_types[m->in_conflict],
 890                                m->lo, m->hi);
 891                 }
 892                 if (m == mpos)
 893                         offset = offsetpos;
 894
 895                 switch (m->type) {
 896                 case Unchanged:
 897                 case AlreadyApplied:
 898                 case Unmatched:
 899                         lineno += printrange(out, a, m->a, m->al, offset);
 900                         break;
 901                 case Extraneous:
 902                         break;
 903                 case Changed:
 904                         lineno += printrange(out, c, m->c, m->cl, offset);
 905                         break;
 906                 case Conflict:
 907                 case End:
 908                         assert(0);
 909                 }
 910                 if (m == mpos)
 911                         rv = lineno;
 912         }
 913         return rv;
 914 }
 915
 916 int save_merge(struct file a, struct file b, struct file c,
 917                struct merge *merger, char *file, int backup)
 918 {
 919         char *replacename = xmalloc(strlen(file) + 20);
 920         char *orignew = xmalloc(strlen(file) + 20);
 921         int fd;
 922         FILE *outfile;
 923         int err = 0;
 924         int lineno = 0;
 925         strcpy(replacename, file);
 926         strcat(replacename, "XXXXXX");
 927         strcpy(orignew, file);
 928         strcat(orignew, ".porig");
 929
 930         fd = mkstemp(replacename);
 931         if (fd < 0) {
 932                 err = -1;
 933                 goto out;
 934         }
 935         outfile = fdopen(fd, "w");
 936         lineno = print_merge(outfile, &a, &b, &c, 0, merger,
 937                              NULL, 0, 0);
 938         fclose(outfile);
 939         if (backup && rename(file, orignew) != 0)
 940                 err = -2;
 941         else if (rename(replacename, file) != 0)
 942                 err = -2;
 943
 944 out:
 945         free(replacename);
 946         free(orignew);
 947         return err < 0 ? err : lineno;
 948 }
 949
 950 int save_tmp_merge(struct file a, struct file b, struct file c,
 951                    struct merge *merger, char **filep,
 952                    struct merge *mpos, int streampos, int offsetpos)
 953 {
 954         int fd;
 955         FILE *outfile;
 956         char *dir, *fname;
 957         int lineno;
 958         int suffix = 0;
 959
 960         if (!*filep) {
 961                 dir = getenv("TMPDIR");
 962                 if (!dir)
 963                         dir = "/tmp";
 964
 965                 asprintf(&fname, "%s/wiggle-tmp-XXXXXX", dir);
 966         } else {
 967                 char *base;
 968                 dir = *filep;
 969                 base = strrchr(dir, '/');
 970                 if (base)
 971                         base++;
 972                 else
 973                         base = dir;
 974                 asprintf(&fname, "%.*stmp-XXXXXX-%s", (int)(base-dir), dir, base);
 975                 suffix = strlen(base)+1;
 976         }
 977         fd = mkstemps(fname, suffix);
 978
 979         if (fd < 0) {
 980                 free(fname);
 981                 *filep = NULL;
 982                 return -1;
 983         }
 984         outfile = fdopen(fd, "w");
 985         lineno = print_merge(outfile, &a, &b, &c, 0, merger,
 986                              mpos, streampos, offsetpos);
 987         fclose(outfile);
 988         *filep = fname;
 989         return lineno;
 990 }